Queue

A comprehensive guide to mastering queue patterns and techniques for Data Structures and Algorithms interviews and competitive programming.

Introduction
Basic Queue Operations
Queue Implementations
BFS and Level-Order Traversal
Sliding Window Techniques
Deque (Double-Ended Queue)
Priority Queue Applications
Monotonic Queue
Queue-Based Algorithms
Advanced Patterns
Problem-Solving Framework
Practice Problems

Introduction

Queues follow the FIFO (First In, First Out) principle and are fundamental for many algorithmic patterns. They're essential for:

Breadth-First Search (BFS) traversals
Level-order processing in trees and graphs
Sliding window problems with deque optimization
Task scheduling and buffering
Stream processing and real-time systems

When to Use Queues

✅ Use when you need:

Process elements in order of arrival
Level-by-level traversal (BFS)
Sliding window with efficient add/remove from both ends
Task scheduling or buffering
Finding shortest paths in unweighted graphs

❌ Avoid when:

Need random access to elements
LIFO behavior is required (use stack instead)
Need frequent middle insertions/deletions

Basic Queue Operations

Standard Queue Interface

class Queue {
    constructor() {
        this.items = [];
        this.front = 0;
        this.rear = 0;
    }

    // Add element to rear
    enqueue(item) {
        this.items[this.rear] = item;
        this.rear++;
    }

    // Remove element from front
    dequeue() {
        if (this.isEmpty()) return undefined;

        const item = this.items[this.front];
        this.items[this.front] = undefined; // Clean up
        this.front++;

        // Reset when queue becomes empty
        if (this.front === this.rear) {
            this.front = 0;
            this.rear = 0;
        }

        return item;
    }

    // Peek at front element
    peek() {
        if (this.isEmpty()) return undefined;
        return this.items[this.front];
    }

    // Check if queue is empty
    isEmpty() {
        return this.front === this.rear;
    }

    // Get queue size
    size() {
        return this.rear - this.front;
    }

    // Clear the queue
    clear() {
        this.items = [];
        this.front = 0;
        this.rear = 0;
    }
}

Time Complexities:

Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
Size: O(1)

Queue Implementations

1. Array-Based Queue (Circular Buffer)

Efficient implementation avoiding array shifting:

class CircularQueue {
    constructor(capacity = 10) {
        this.items = new Array(capacity);
        this.front = 0;
        this.rear = 0;
        this.size = 0;
        this.capacity = capacity;
    }

    enqueue(item) {
        if (this.isFull()) {
            throw new Error("Queue is full");
        }

        this.items[this.rear] = item;
        this.rear = (this.rear + 1) % this.capacity;
        this.size++;
    }

    dequeue() {
        if (this.isEmpty()) return undefined;

        const item = this.items[this.front];
        this.items[this.front] = undefined;
        this.front = (this.front + 1) % this.capacity;
        this.size--;

        return item;
    }

    isFull() {
        return this.size === this.capacity;
    }

    isEmpty() {
        return this.size === 0;
    }

    peek() {
        return this.isEmpty() ? undefined : this.items[this.front];
    }
}

2. Linked List-Based Queue

Dynamic size with efficient operations:

class QueueNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedQueue {
    constructor() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    enqueue(val) {
        const newNode = new QueueNode(val);

        if (this.rear) {
            this.rear.next = newNode;
        } else {
            this.front = newNode; // First element
        }

        this.rear = newNode;
        this.size++;
    }

    dequeue() {
        if (!this.front) return undefined;

        const val = this.front.val;
        this.front = this.front.next;

        if (!this.front) {
            this.rear = null; // Queue became empty
        }

        this.size--;
        return val;
    }

    peek() {
        return this.front ? this.front.val : undefined;
    }

    isEmpty() {
        return this.front === null;
    }
}

3. Two-Stack Queue Implementation

Queue using two stacks (interview favorite):

class TwoStackQueue {
    constructor() {
        this.inStack = [];   // For enqueue operations
        this.outStack = [];  // For dequeue operations
    }

    enqueue(item) {
        this.inStack.push(item);
    }

    dequeue() {
        this._moveElements();
        return this.outStack.pop();
    }

    peek() {
        this._moveElements();
        return this.outStack[this.outStack.length - 1];
    }

    isEmpty() {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }

    size() {
        return this.inStack.length + this.outStack.length;
    }

    // Move elements from inStack to outStack when needed
    _moveElements() {
        if (this.outStack.length === 0) {
            while (this.inStack.length > 0) {
                this.outStack.push(this.inStack.pop());
            }
        }
    }
}

Amortized Analysis: Each element is moved at most twice, so average O(1) per operation.

BFS and Level-Order Traversal

1. Binary Tree Level-Order Traversal

Problem: Traverse tree level by level, returning each level as a separate array.

function levelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);

            // Add children to queue for next level
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
    }

    return result;
}

Time Complexity: O(n) | Space Complexity: O(w) where w is maximum width

2. Zigzag Level Order Traversal

Problem: Traverse tree in zigzag pattern (left-to-right, then right-to-left alternately).

function zigzagLevelOrder(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];
    let leftToRight = true;

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            // Add to front or back based on direction
            if (leftToRight) {
                currentLevel.push(node.val);
            } else {
                currentLevel.unshift(node.val);
            }

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        result.push(currentLevel);
        leftToRight = !leftToRight; // Flip direction
    }

    return result;
}

3. Binary Tree Right Side View

Problem: Return values of nodes you can see from the right side of tree.

function rightSideView(root) {
    if (!root) return [];

    const result = [];
    const queue = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            // Last node in level is visible from right
            if (i === levelSize - 1) {
                result.push(node.val);
            }

            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return result;
}

4. Graph BFS (Shortest Path)

Problem: Find shortest path in unweighted graph.

function shortestPath(graph, start, target) {
    if (start === target) return 0;

    const queue = [[start, 0]]; // [node, distance]
    const visited = new Set([start]);

    while (queue.length > 0) {
        const [node, distance] = queue.shift();

        // Check all neighbors
        for (const neighbor of graph[node] || []) {
            if (neighbor === target) {
                return distance + 1;
            }

            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push([neighbor, distance + 1]);
            }
        }
    }

    return -1; // Path not found
}

5. Word Ladder (BFS Application)

Problem: Find minimum transformation sequence from start word to end word.

function ladderLength(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const queue = [[beginWord, 1]]; // [word, transformations]
    const visited = new Set([beginWord]);

    while (queue.length > 0) {
        const [word, steps] = queue.shift();

        if (word === endWord) {
            return steps;
        }

        // Try all possible one-letter transformations
        for (let i = 0; i < word.length; i++) {
            for (let c = 97; c <= 122; c++) { // 'a' to 'z'
                const newChar = String.fromCharCode(c);
                if (newChar === word[i]) continue;

                const newWord = word.slice(0, i) + newChar + word.slice(i + 1);

                if (wordSet.has(newWord) && !visited.has(newWord)) {
                    visited.add(newWord);
                    queue.push([newWord, steps + 1]);
                }
            }
        }
    }

    return 0; // No transformation possible
}

Sliding Window Techniques

1. Sliding Window Maximum (Deque)

Problem: Find maximum in each sliding window of size k.

function maxSlidingWindow(nums, k) {
    const result = [];
    const deque = []; // Stores indices

    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside current window
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }

        // Remove indices with smaller values (maintain decreasing order)
        while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        // Add maximum to result when window is complete
        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

Time Complexity: O(n) | Space Complexity: O(k)

💡 Key Insight: Deque maintains indices in decreasing order of their values, so front always has the maximum.

2. First Negative in Window

Problem: Find first negative number in each sliding window.

function firstNegativeInWindow(arr, k) {
    const result = [];
    const queue = []; // Stores indices of negative numbers

    for (let i = 0; i < arr.length; i++) {
        // Remove indices outside current window
        while (queue.length > 0 && queue[0] <= i - k) {
            queue.shift();
        }

        // Add current index if number is negative
        if (arr[i] < 0) {
            queue.push(i);
        }

        // Add result when window is complete
        if (i >= k - 1) {
            if (queue.length > 0) {
                result.push(arr[queue[0]]);
            } else {
                result.push(0); // No negative number in window
            }
        }
    }

    return result;
}

3. Generate Binary Numbers

Problem: Generate binary representations of numbers 1 to n using queue.

function generateBinary(n) {
    if (n <= 0) return [];

    const result = [];
    const queue = ["1"];

    for (let i = 0; i < n; i++) {
        const current = queue.shift();
        result.push(current);

        // Generate next binary numbers by appending 0 and 1
        queue.push(current + "0");
        queue.push(current + "1");
    }

    return result;
}

Pattern Recognition: Each binary number generates two new numbers by appending 0 and 1.

Deque (Double-Ended Queue)

JavaScript Deque Implementation

class Deque {
    constructor() {
        this.items = [];
        this.front = 0;
        this.rear = 0;
    }

    // Add to front
    addFront(item) {
        this.front--;
        this.items[this.front] = item;
    }

    // Add to rear
    addRear(item) {
        this.items[this.rear] = item;
        this.rear++;
    }

    // Remove from front
    removeFront() {
        if (this.isEmpty()) return undefined;

        const item = this.items[this.front];
        this.items[this.front] = undefined;
        this.front++;

        if (this.front === this.rear) {
            this.front = 0;
            this.rear = 0;
        }

        return item;
    }

    // Remove from rear
    removeRear() {
        if (this.isEmpty()) return undefined;

        this.rear--;
        const item = this.items[this.rear];
        this.items[this.rear] = undefined;

        if (this.front === this.rear) {
            this.front = 0;
            this.rear = 0;
        }

        return item;
    }

    peekFront() {
        return this.isEmpty() ? undefined : this.items[this.front];
    }

    peekRear() {
        return this.isEmpty() ? undefined : this.items[this.rear - 1];
    }

    isEmpty() {
        return this.front === this.rear;
    }

    size() {
        return this.rear - this.front;
    }
}

Palindrome Checker with Deque

function isPalindrome(str) {
    const deque = new Deque();
    const cleanStr = str.toLowerCase().replace(/[^a-z0-9]/g, '');

    // Add all characters to deque
    for (const char of cleanStr) {
        deque.addRear(char);
    }

    // Compare characters from both ends
    while (deque.size() > 1) {
        if (deque.removeFront() !== deque.removeRear()) {
            return false;
        }
    }

    return true;
}

Priority Queue Applications

1. Priority Queue with Heap

class PriorityQueue {
    constructor(compareFunc = (a, b) => a - b) {
        this.heap = [];
        this.compare = compareFunc;
    }

    enqueue(item) {
        this.heap.push(item);
        this._bubbleUp(this.heap.length - 1);
    }

    dequeue() {
        if (this.isEmpty()) return undefined;

        const root = this.heap[0];
        const last = this.heap.pop();

        if (!this.isEmpty()) {
            this.heap[0] = last;
            this._bubbleDown(0);
        }

        return root;
    }

    peek() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    size() {
        return this.heap.length;
    }

    _bubbleUp(index) {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);

            if (this.compare(this.heap[index], this.heap[parentIndex]) >= 0) {
                break;
            }

            [this.heap[index], this.heap[parentIndex]] =
            [this.heap[parentIndex], this.heap[index]];

            index = parentIndex;
        }
    }

    _bubbleDown(index) {
        while (true) {
            let minIndex = index;
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;

            if (leftChild < this.heap.length &&
                this.compare(this.heap[leftChild], this.heap[minIndex]) < 0) {
                minIndex = leftChild;
            }

            if (rightChild < this.heap.length &&
                this.compare(this.heap[rightChild], this.heap[minIndex]) < 0) {
                minIndex = rightChild;
            }

            if (minIndex === index) break;

            [this.heap[index], this.heap[minIndex]] =
            [this.heap[minIndex], this.heap[index]];

            index = minIndex;
        }
    }
}

2. Task Scheduler

Problem: Schedule tasks with cooldown period to minimize idle time.

function leastInterval(tasks, n) {
    // Count frequency of each task
    const taskCount = new Map();
    for (const task of tasks) {
        taskCount.set(task, (taskCount.get(task) || 0) + 1);
    }

    // Max heap based on frequency
    const pq = new PriorityQueue((a, b) => b - a);
    for (const count of taskCount.values()) {
        pq.enqueue(count);
    }

    let time = 0;
    const queue = []; // [count, availableTime]

    while (!pq.isEmpty() || queue.length > 0) {
        time++;

        // Move tasks back to priority queue when cooldown is over
        if (queue.length > 0 && queue[0][1] === time) {
            const count = queue.shift()[0];
            pq.enqueue(count);
        }

        // Execute highest frequency task
        if (!pq.isEmpty()) {
            const count = pq.dequeue() - 1;
            if (count > 0) {
                queue.push([count, time + n + 1]);
            }
        }
    }

    return time;
}

3. Top K Frequent Elements

Problem: Find k most frequent elements in array.

function topKFrequent(nums, k) {
    // Count frequencies
    const freqMap = new Map();
    for (const num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }

    // Min heap of size k
    const pq = new PriorityQueue((a, b) => a[1] - b[1]);

    for (const [num, freq] of freqMap.entries()) {
        pq.enqueue([num, freq]);

        if (pq.size() > k) {
            pq.dequeue();
        }
    }

    const result = [];
    while (!pq.isEmpty()) {
        result.push(pq.dequeue()[0]);
    }

    return result.reverse();
}

Monotonic Queue

A queue that maintains elements in monotonic (increasing/decreasing) order.

1. Largest Rectangle in Histogram

Problem: Find area of largest rectangle in histogram.

function largestRectangleArea(heights) {
    const stack = []; // Monotonic increasing stack (acts like queue)
    let maxArea = 0;

    for (let i = 0; i <= heights.length; i++) {
        const currentHeight = i === heights.length ? 0 : heights[i];

        while (stack.length > 0 && heights[stack[stack.length - 1]] > currentHeight) {
            const height = heights[stack.pop()];
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    return maxArea;
}

2. Sliding Window Minimum

Problem: Find minimum in each sliding window using monotonic deque.

function slidingWindowMinimum(nums, k) {
    const result = [];
    const deque = []; // Stores indices in increasing order of values

    for (let i = 0; i < nums.length; i++) {
        // Remove indices outside window
        while (deque.length > 0 && deque[0] <= i - k) {
            deque.shift();
        }

        // Maintain increasing order
        while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
            deque.pop();
        }

        deque.push(i);

        if (i >= k - 1) {
            result.push(nums[deque[0]]);
        }
    }

    return result;
}

Queue-Based Algorithms

1. Breadth-First Search Template

function bfsTemplate(start, isTarget, getNeighbors) {
    const queue = [start];
    const visited = new Set([start]);
    const parent = new Map();
    let level = 0;

    while (queue.length > 0) {
        const levelSize = queue.length;

        // Process all nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();

            if (isTarget(node)) {
                return reconstructPath(node, parent);
            }

            for (const neighbor of getNeighbors(node)) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    parent.set(neighbor, node);
                    queue.push(neighbor);
                }
            }
        }

        level++;
    }

    return null; // Target not found
}

function reconstructPath(target, parent) {
    const path = [];
    let current = target;

    while (current !== undefined) {
        path.unshift(current);
        current = parent.get(current);
    }

    return path;
}

2. Multi-Source BFS

Problem: Find distance from nearest obstacle/source for all cells.

function nearestObstacle(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const queue = [];
    const distances = Array(rows).fill().map(() => Array(cols).fill(Infinity));

    // Add all obstacles to queue as starting points
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === 1) { // Obstacle
                queue.push([i, j, 0]);
                distances[i][j] = 0;
            }
        }
    }

    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    while (queue.length > 0) {
        const [row, col, dist] = queue.shift();

        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;

            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                const newDist = dist + 1;

                if (newDist < distances[newRow][newCol]) {
                    distances[newRow][newCol] = newDist;
                    queue.push([newRow, newCol, newDist]);
                }
            }
        }
    }

    return distances;
}

3. Rotting Oranges

Problem: Find minimum time for all oranges to rot.

function orangesRotting(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const queue = [];
    let freshCount = 0;

    // Find initial rotten oranges and count fresh ones
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 2) {
                queue.push([i, j, 0]); // [row, col, time]
            } else if (grid[i][j] === 1) {
                freshCount++;
            }
        }
    }

    if (freshCount === 0) return 0;

    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let maxTime = 0;

    while (queue.length > 0) {
        const [row, col, time] = queue.shift();

        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;

            if (newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                grid[newRow][newCol] === 1) {

                grid[newRow][newCol] = 2; // Rot the orange
                freshCount--;
                maxTime = Math.max(maxTime, time + 1);
                queue.push([newRow, newCol, time + 1]);
            }
        }
    }

    return freshCount === 0 ? maxTime : -1;
}

Advanced Patterns

1. Queue Reconstruction by Height

Problem: Reconstruct queue based on height and people in front.

function reconstructQueue(people) {
    // Sort by height desc, then by k asc
    people.sort((a, b) => {
        if (a[0] !== b[0]) {
            return b[0] - a[0]; // Taller first
        }
        return a[1] - b[1]; // Smaller k first
    });

    const result = [];

    // Insert each person at position k
    for (const person of people) {
        result.splice(person[1], 0, person);
    }

    return result;
}

2. Design Hit Counter

Problem: Count hits in the last 5 minutes using queue.

class HitCounter {
    constructor() {
        this.hits = []; // Queue of timestamps
    }

    hit(timestamp) {
        this.hits.push(timestamp);
        this._removeOldHits(timestamp);
    }

    getHits(timestamp) {
        this._removeOldHits(timestamp);
        return this.hits.length;
    }

    _removeOldHits(timestamp) {
        // Remove hits older than 5 minutes (300 seconds)
        while (this.hits.length > 0 &&
               this.hits[0] <= timestamp - 300) {
            this.hits.shift();
        }
    }
}

3. Shortest Bridge (BFS + DFS)

Problem: Find shortest bridge between two islands.

function shortestBridge(grid) {
    const rows = grid.length;
    const cols = grid[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    // Find first island using DFS
    const firstIsland = [];
    let found = false;

    for (let i = 0; i < rows && !found; i++) {
        for (let j = 0; j < cols && !found; j++) {
            if (grid[i][j] === 1) {
                dfs(i, j);
                found = true;
            }
        }
    }

    function dfs(row, col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols ||
            grid[row][col] !== 1) {
            return;
        }

        grid[row][col] = 2; // Mark as visited
        firstIsland.push([row, col]);

        for (const [dr, dc] of directions) {
            dfs(row + dr, col + dc);
        }
    }

    // BFS from first island to find second island
    const queue = [...firstIsland.map(pos => [...pos, 0])];

    while (queue.length > 0) {
        const [row, col, distance] = queue.shift();

        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;

            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                if (grid[newRow][newCol] === 1) {
                    return distance; // Found second island
                } else if (grid[newRow][newCol] === 0) {
                    grid[newRow][newCol] = 2; // Mark as visited
                    queue.push([newRow, newCol, distance + 1]);
                }
            }
        }
    }

    return -1; // Should never reach here
}

4. Design Circular Queue

Problem: Implement a circular queue with fixed size.

class MyCircularQueue {
    constructor(k) {
        this.size = k;
        this.queue = new Array(k);
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }

    enQueue(value) {
        if (this.isFull()) return false;

        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.size;
        this.count++;
        return true;
    }

    deQueue() {
        if (this.isEmpty()) return false;

        this.queue[this.front] = undefined;
        this.front = (this.front + 1) % this.size;
        this.count--;
        return true;
    }

    Front() {
        return this.isEmpty() ? -1 : this.queue[this.front];
    }

    Rear() {
        if (this.isEmpty()) return -1;
        const rearIndex = (this.rear - 1 + this.size) % this.size;
        return this.queue[rearIndex];
    }

    isEmpty() {
        return this.count === 0;
    }

    isFull() {
        return this.count === this.size;
    }
}

5. Moving Average from Data Stream

Problem: Calculate moving average of last size numbers.

class MovingAverage {
    constructor(size) {
        this.size = size;
        this.queue = [];
        this.sum = 0;
    }

    next(val) {
        this.queue.push(val);
        this.sum += val;

        // Remove oldest element if queue exceeds size
        if (this.queue.length > this.size) {
            this.sum -= this.queue.shift();
        }

        return this.sum / this.queue.length;
    }
}

Problem-Solving Framework

Queue Pattern Recognition

Level-by-level processing → BFS with queue
Shortest path in unweighted graph → BFS
Sliding window maximum/minimum → Deque
First/last element in window → Queue with cleanup
Multi-source shortest path → Multi-source BFS
Tree/graph traversal by levels → Level-order BFS

Step-by-Step Approach

function queueProblemTemplate(input) {
    // 1. Identify the pattern
    // - BFS traversal?
    // - Sliding window?
    // - Level processing?

    // 2. Choose appropriate queue type
    const queue = []; // or Deque, PriorityQueue

    // 3. Initialize with starting state
    queue.push(initialState);
    const visited = new Set(); // if needed

    // 4. Process until queue is empty
    while (queue.length > 0) {
        // Level processing (optional)
        const levelSize = queue.length;

        for (let i = 0; i < levelSize; i++) {
            const current = queue.shift();

            // Process current element
            if (isTarget(current)) {
                return result;
            }

            // Add neighbors/next states
            for (const next of getNext(current)) {
                if (!visited.has(next)) {
                    visited.add(next);
                    queue.push(next);
                }
            }
        }
    }

    return defaultResult;
}

Practice Problems

Beginner Level

Implement Queue using Stacks
Binary Tree Level Order Traversal
First Negative Number in Window
Generate Binary Numbers
Design Circular Queue

Intermediate Level

Sliding Window Maximum
Rotting Oranges
Word Ladder
Binary Tree Zigzag Traversal
Task Scheduler
Moving Average from Data Stream

Advanced Level

Shortest Bridge
Queue Reconstruction by Height
Design Hit Counter
Largest Rectangle in Histogram
Minimum Window Substring
Cut Off Trees for Golf Event

Expert Level

Alien Dictionary (Topological Sort + Queue)
Bus Routes (BFS with queue)
Sliding Window Median (Two heaps + deque)
Jump Game IV (BFS optimization)
Race Car (BFS state space)

Time Complexity Summary

Operation/Algorithm	Time Complexity	Space Complexity	Use Case
Queue Operations	O(1)	O(1)	Basic enqueue/dequeue
BFS Traversal	O(V + E)	O(V)	Graph/tree traversal
Level Order	O(n)	O(w)	Tree level processing
Sliding Window Max	O(n)	O(k)	Window optimization
Priority Queue Ops	O(log n)	O(n)	Heap-based operations
Multi-source BFS	O(V + E)	O(V)	Multiple starting points

Common Patterns Summary

1. BFS Template

const queue = [start];
const visited = new Set([start]);

while (queue.length > 0) {
    const node = queue.shift();
    // Process node
    for (const neighbor of getNeighbors(node)) {
        if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
        }
    }
}

2. Level Processing Template

while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];

    for (let i = 0; i < levelSize; i++) {
        const node = queue.shift();
        currentLevel.push(node.val);
        // Add children
    }

    result.push(currentLevel);
}

3. Sliding Window with Deque

const deque = [];
for (let i = 0; i < arr.length; i++) {
    // Remove outside window
    while (deque.length > 0 && deque[0] <= i - k) {
        deque.shift();
    }

    // Maintain monotonic property
    while (deque.length > 0 && condition) {
        deque.pop();
    }

    deque.push(i);
    if (i >= k - 1) result.push(arr[deque[0]]);
}

4. Multi-source BFS

const queue = [];
// Add all sources
for (const source of sources) {
    queue.push([source, 0]);
    visited.add(source);
}

while (queue.length > 0) {
    const [node, distance] = queue.shift();
    // Process and add neighbors
}

Key Takeaways

✅ Advantages of Queues

FIFO ordering ensures proper sequence
Level-by-level processing for trees/graphs
Optimal for BFS and shortest path problems
Sliding window optimization with deque
Efficient buffering and task scheduling

⚠️ Common Pitfalls

Forgetting to check empty queue before dequeue
Not handling edge cases (empty input, single element)
Incorrect level processing in BFS
Memory leaks from not cleaning up references
Wrong queue type for the problem

🎯 Best Practices

Use appropriate queue implementation for the problem
Validate input and handle edge cases
Choose right data structure: Array, LinkedList, or specialized queue
Consider space optimization for large datasets
Test with various inputs including edge cases

🧠 Memory Tricks

"Queue = Line" → First come, first served
BFS = Queue → Level by level exploration
Deque = Double power → Add/remove from both ends
Priority Queue = VIP line → Most important first
Sliding window = Moving frame → Deque for optimization

Quick Reference Cheat Sheet

// Basic Queue Operations
queue.push(item);      // enqueue
queue.shift();         // dequeue
queue[0];             // peek front

// BFS Pattern
while (queue.length > 0) {
    const node = queue.shift();
    // process node
    // add neighbors to queue
}

// Level Order Pattern
while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
        const node = queue.shift();
        // process level
    }
}

// Sliding Window Maximum (Deque)
while (deque[0] <= i - k) deque.shift();
while (nums[deque[deque.length-1]] <= nums[i]) deque.pop();
deque.push(i);

// Priority Queue (Min Heap)
const pq = new PriorityQueue((a, b) => a - b);
pq.enqueue(item);
pq.dequeue(); // returns minimum

Table of Contents​

Introduction​

When to Use Queues​

Basic Queue Operations​

Standard Queue Interface​

Queue Implementations​

1. Array-Based Queue (Circular Buffer)​

2. Linked List-Based Queue​

3. Two-Stack Queue Implementation​

BFS and Level-Order Traversal​

1. Binary Tree Level-Order Traversal​

2. Zigzag Level Order Traversal​

3. Binary Tree Right Side View​

4. Graph BFS (Shortest Path)​

5. Word Ladder (BFS Application)​

Sliding Window Techniques​

1. Sliding Window Maximum (Deque)​

2. First Negative in Window​

3. Generate Binary Numbers​

Deque (Double-Ended Queue)​

JavaScript Deque Implementation​

Palindrome Checker with Deque​

Priority Queue Applications​

1. Priority Queue with Heap​

2. Task Scheduler​

3. Top K Frequent Elements​

Monotonic Queue​

1. Largest Rectangle in Histogram​

2. Sliding Window Minimum​

Queue-Based Algorithms​

1. Breadth-First Search Template​

2. Multi-Source BFS​

3. Rotting Oranges​

Advanced Patterns​

1. Queue Reconstruction by Height​

2. Design Hit Counter​

3. Shortest Bridge (BFS + DFS)​

4. Design Circular Queue​

5. Moving Average from Data Stream​

Problem-Solving Framework​

Queue Pattern Recognition​

Step-by-Step Approach​

Practice Problems​

Beginner Level​

Intermediate Level​

Advanced Level​

Expert Level​

Time Complexity Summary​

Common Patterns Summary​

1. BFS Template​

2. Level Processing Template​

3. Sliding Window with Deque​

4. Multi-source BFS​

Key Takeaways​

✅ Advantages of Queues​

⚠️ Common Pitfalls​

🎯 Best Practices​

🧠 Memory Tricks​

Quick Reference Cheat Sheet​

Table of Contents